package bin_tree.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author shkstart
 * @create 2022-10-21-20:15
 */
public class Num94 {
//    基于栈的迭代
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //两个判断条件是为了在cur为空时可以继续循环
        //但同时要判断root是否为空
        while(cur!=null||(!stack.isEmpty())){
            //从根节点一直向左子树压栈,知道最左边的叶子节点
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }//当小循环结束后,cur是最坐下叶子节点的左树(此时为null)
            //所以栈顶元素的最左下的叶子节点
//            出栈 访问根节点
            cur = stack.pop();
            ret.add(cur.val);
//            访问右子树
            cur= cur.right;
        }
        return ret;
    }
}
